Linear Algebra

The set of vectors \( \{ \mathbf{v}_1, \dots, \mathbf{v}_k \} \) is said to be linearly independent if \[ a_1\mathbf{v}_1 + a_2\mathbf{v}_2 + \cdots + a_k\mathbf{v}_k = \mathbf{0} \implies a_1 = a_2 = \cdots = a_k = 0 \] where \( a_i \) are the elements of the field associated with the underlying vector space.

• If every nonempty finite subset of vectors is linearly independent.

• No rectangular identity.

• A matrix which differs from the identity matrix by one of the elementary row operations, which in turn represents that single row operation by multiplying on the left.
• Elementary matrix - Wikipedia

\[ \exists k \in \mathbb{N}, N^k = 0. \] The smallest such \( k \) is called the index of \( N \).

Zeros above the superdiagonal or below the subdiagonal.

• It is the matrix that preserves the magnitudes of vectors.
• It contains rotations and reflections.

• How to "diagonally" think about rotations. - YouTube
  • Orthogonal matrix is complex diagonalizable
• See infinite groups

• Matrix with \(n\) rows and \(m\) columns.

• First Minors of a square matrix \( A \) are the determinants of submatrices of \( A \) with one row and one column removed.
• n-th minors are with n rows and n columns removed.

• The row indices \( I \) and column indices \( J \) of the original matrix that are used in minor is the same \( I = J \).

• The square upper-left submatrix.

\[ C_{ij} = (-1)^{i+j} M_{ij} \] where \( M_{ij} \) is the first minor with \( i\)-th row and \(j\)-th column removed.

Cofactor matrix of a matrix \( A \) is the matrix with its \( i,j \) entry is the cofactor \( C_{ij} \) of \( A \).

• An \(m\times n\) matrix \(A\) over a field \(K\) is called invertible if:
  • \[ \exists B\in K^{n\times m}, AB = I_m\land BA = I_n \]
• That is, both left inverse and right inverse exists and they are the same, in which case it is called the inverse matrix.

• It is necessary that \(m=n\).
• Inverse matrix can be obtained from the cofactor matrix \( C \) with: \[ A^{-1} = \frac{1}{\det A} C^{\rm T} \]

• Matrix Inversion Theorem

• Pseudo inverse matrix \(A^+\) is a matrix satisfying: \[ \forall v \in \text{rowspace}(A), A^+Av = v. \]
  • In the case of left inverse the kernel was trivial and the cokernel was nontrivial, and in the case of right inverse the kernel was nontrivial and the cokernel was trivial.
  • In general, for a matrix with nontrivial kernel and nontrivial cokernel, pseudo inverse can be calculated using the singular value decomposition: \[ A = U\Sigma V^\top \implies A^+ = V\Sigma^+ U^\top \]
    • where \(\sigma^+\) is the diagonal matrix with reciprocal entries, with zeroes untact.

• The determinant of an square matrix \(A\) is the sum of \(a_{ij}C_{ij}\) in along any row or column: \[ \det(A) = \sum_{i=1}^na_{ij}C_{ij} = \sum_{j=1}^na_{ij}C_{ij} \] where \(C_{ij}\) are the cofactors.

• For \(A, B \in \mathbb{C}^{n\times n}\) with ordered singular values \((\sigma_i)\) and \((\tau_i)\), \[ |\mathrm{tr}(AB)| \le \sum_{i=1}^n \sigma_i\tau_i \]
• with equality if and only if \(A\) and \(B\) share singular values.

• Applying the formula to find the inverse matrix , \[ I = AA^{-1} \]
• One get: \[ (A^{-1})_{ij} = \frac{\det(\mathbf{a}_1, \dots, \overbrace{\mathbf{e}_j}^\text{$i$th column}, \dots, \mathbf{a}_n)}{\det(\mathbf{a}_1,\dots, \mathbf{a}_n )} = \frac{C_{ij}}{\det(A)} \]
• where \(C_{ij}\) is the cofactor matrix.

• Using homogeneous coordinates, let the two plane:

  \begin{cases} \alpha_1\tilde{x} + \alpha_2\tilde{y} + \alpha_3\tilde{z} = 0\\ \beta_1\tilde{x} + \beta_2\tilde{y} + \beta_3\tilde{z} = 0 \end{cases}
• be two projective lines on a projective plane.

• Note that dehomogenizing through dividing both side by \(\tilde{z}\):

  \begin{cases} \alpha_1x+ \alpha_2y + \alpha_3 = 0\\ \beta_1x + \beta_2y + \beta_3 = 0 \end{cases}
  • with \(x = \tilde{x}/\tilde{z}, y = \tilde{y}/\tilde{z}\), \(z = \tilde{z}/\tilde{z} = 1\), given that \(\tilde{z}\neq 0\).
  • Or just add a restriction to the homogeneous coordinate since it has extra degree of freedom: \(\tilde{z} = 1\).
• The affine transformation matrix is \[ \begin{bmatrix} 0 \\ 0\\1\end{bmatrix} = \begin{bmatrix} \alpha_1 & \alpha_2 & \alpha_3 \\ \beta_1 & \beta_2 & \beta_3\\ 0 & 0 & 1 \end{bmatrix}\begin{bmatrix} x \\ y \\ 1 \end{bmatrix}, \]
• By the Cramer's rule
• \[ x = \frac{\begin{vmatrix} 0 & \alpha_2 & \alpha_3 \\ 0 & \beta_2 & \beta_3\\ 1 & 0 & 1 \end{vmatrix}}{\begin{vmatrix} \alpha_1 & \alpha_2 & \alpha_3 \\ \beta_1 & \beta_2 & \beta_3\\ 0 & 0 & 1 \end{vmatrix}} = \frac{\alpha_2\beta_3 - \alpha_3\beta_2}{\alpha_1\beta_2 - \alpha_2\beta_1}, \quad y = \frac{\begin{vmatrix} \alpha_1 & 0 & \alpha_3 \\ \beta_1 & 0 & \beta_3\\ 0 & 1 & 1 \end{vmatrix}}{\begin{vmatrix} \alpha_1 & \alpha_2 & \alpha_3 \\ \beta_1 & \beta_2 & \beta_3\\ 0 & 0 & 1 \end{vmatrix}} = \frac{\alpha_3\beta_1 - \alpha_1\beta_3}{\alpha_1\beta_2 - \alpha_2\beta_1} \]
• Finally, by substituting the homogeneous coordinate back: \[ \frac{\tilde{x}}{\alpha_2\beta_3 - \alpha_3\beta_2} = \frac{\tilde{y}}{\alpha_3\beta_1 - \alpha_1\beta_3} = \frac{\tilde{z}}{\alpha_1\beta_2 - \alpha_2\beta_1}.\ \square \]

• Swap: Swap two rows
  • Determinant gets multiplied by \(-1\)
• Scale: Scalar multiply a row by a nonzero constant
  • Determinant gets multiplied by that scalar
• Pivot: Add scalar multiple of a row to another row
  • Determinant does not change

• It is defined to be the result of Gaussian elimination.
• Lower left-hand corner of the matrix is filled with zeros as much as possible.
• It is a upper triangular matrix with the leading coefficients being the pivots.

• Process of reducing to the reduced row echelon form.
• If the matrix is invertible, then this would reduce the matrix into the identity matrix.
• This can be used to find the inverse of a matrix by augmenting it with an identity matrix.

• Entrywise Sum

• The direct sum of \( m\times n \) matrix \( A \) and \( p\times q \) matrix \( B \) is a \( (m+p)\times (n+q) \) matrix: \[ A\oplus B = \begin{bmatrix} A & 0 \\ 0 & B \end{bmatrix}. \]

• The Kronecker sum of \( n\times n \) matrix \( A \) and \( m\times m \) matrix \( B \) is: \[ A\oplus B = A\otimes I_m + I_n \otimes B \] where \(\otimes\) is the Kronecker product.

• Matrix Direct Product
• \(\otimes\)
• Special tensor product with a standard choice of basis.
• If \(A\) is an \(m\times n\) matrix and \(B\) is a \(p\times q\) matrix, then the Kronecker product is a \(pm\times qn\) matrix with: \[ (A\otimes B)_{pr+v,qs+w} = a_{rs}b_{vw}. \]
• It produces a block matrix

• Element-wise Product, Entrywise Product, Schur Product
• \(\odot\), \(\circ\)
• For two matrices \(A\) and \(B\) of the same dimension, the Hadamard product is a matrix of the same dimension with:\ \[ (A\odot B)_{ij} = a_{ij}b_{ij}. \]

• If \(A\) is a Hermitian matrix, then all eigenvalues of \(A\) are real, and its eigenvectors are orthonormal basis that spans the entire vector space.

• \(A\) is normal if and only if there exists a unitary matrix \(U\) such that: \[ A = UDU^\dagger \] where \(D\) is a diagonal matrix.
• This is a special case of the Schur decomposition.

• Assume that for a symmetric matrix \(C\in M_{n-1\times n-1}(\mathbb{R})\), there exists an orthogonal matrix \(Q\) such that \(Q^{-1}CQ\) is a diagonal matrix.
• Then for a symmetric matrix \(A\in M_{n\times n}(\mathbb{R})\), there exists: \[ R = P\begin{bmatrix}1 & 0 \\ 0 & Q\end{bmatrix} \] where \(P\) is the orthogonal matrix constructed from one of the eigenvectors.
• This transforms \(A\) into a diagonal matrix: \[ R^{-1}AR = \begin{bmatrix} 1 & 0 \\ 0 & Q^{-1}\end{bmatrix}\begin{bmatrix} \lambda_i & 0 \\ 0 & C\end{bmatrix}\begin{bmatrix} 1 & 0 \\ 0 & Q\end{bmatrix} = \begin{bmatrix} \lambda_i & 0 \\ 0 & Q^{-1}CQ \end{bmatrix}. \]

• \[ \det\begin{bmatrix}A & 0 \\ C & D \end{bmatrix} = \det(A)\det(D) = \det\begin{bmatrix} A & B \\ 0 & D \end{bmatrix} \]
  • This is proven by the Leibniz formula for determinants.
  • A block matrix can be can be transformed into upper or lower block triangular matrix by the block Gaussian elimination.
• If \(A\) is invertible: \[ \det(M) = \det\begin{bmatrix} A & B \\ C & D \end{bmatrix} = \det(A) \det(M/A). \]
• If \(D\) is invertible: \[ \det(M) = \det\begin{bmatrix} A & B \\ C & D \end{bmatrix} = \det(M/D) \det(D). \]
• If the blocks are square matrices of the same size:
  • If \(C\) and \(D\) commute:
    • \[ \det\begin{bmatrix} A & B \\ C & D \end{bmatrix} = \det(AD-BC). \]

• One of the two matrices in the block-diagonal matrix is invertible exactly when the other is.

• A \((p+q) \times (p+q)\) matrix \(M\) is a block matrix such that: \[ M = \begin{bmatrix} A_{p\times p} & B_{p\times q} \\ C_{q\times p} & D_{q\times q} \end{bmatrix}. \]
• If \(D\) is invertible, then the Schur complement of the block \(D\) of the matrix \(M\) is the \(p\times p\) matrix: \[ M/D = A-BD^{-1}C. \]
• If \(A\) is invertible, then the Schur complement of the block \(A\) of the matrix \(M\) is the \(q\times q\) matrix: \[ M/A = D - CA^{-1}B. \]

• If \(D\) is invertible:

  \begin{bmatrix} A & B \\ C & D \end{bmatrix} \rightsquigarrow \begin{bmatrix} A & B \\ C & D \end{bmatrix}\begin{bmatrix} I_p & 0 \\ -D^{-1}C & I_q \end{bmatrix} = \begin{bmatrix} M/D & B \\ 0 & D \end{bmatrix}

• If \(A\) is invertible:

  \begin{bmatrix} A & B \\ C & D \end{bmatrix} \rightsquigarrow \begin{bmatrix} A & B \\ C & D \end{bmatrix}\begin{bmatrix} I_p & -A^{-1}B \\ 0 & I_q \end{bmatrix} = \begin{bmatrix} A & 0 \\ C & M/A \end{bmatrix}

• From a system of linear equations with invertible submatrix \(A\):

  \begin{bmatrix} A & B \\ C & D \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} u \\ v \end{bmatrix}
• Since \(x = A^{-1}(u-By)\) from the first equation, the second equation reduces to: \[ (D-CA^{-1}B)y = v-CA^{-1}u. \]
  • Alternatively, this can be thought of as applying the inverse of the first matrix in the block LDU decomposition on both side.
• Then \(y = (M/A)^{-1}(v-CA^{-1}u)\).
• Substitute this into the first equation yields: \[ x=(A^{-1} + A^{-1}B(M/A)^{-1}CA^{-1})u - A^{-1}B(M/A)^{-1}v. \]

• Start with \(IA\), where \(I\) is the identity matrix. -

Starting from the first column of \(I\), fill each entry with \(i_{n1}\), such that \(a_{11}i_{n1}=a_{n1}\), and perform row operation, \(\mathrm{row}_n\rightsquigarrow\mathrm{row}_n-i_{ni}\mathrm{row}_1\), on \(A\) - Repeat the process for the subsequent columns

• The computation can be done either Gram-Schmidt process, Householder

transformations, or Givens rotations.

• It is linear operator on a finite-dimensional vector space represented by a Jordan matrix.

• It is used to analyze the non-diagonalizable matrices—defective matrices.
  • For a defective matrix \(A\) there exists an invertible matrix \(p\) such that: \[ J = P^{-1}AP. \]

• 28. Similar Matrices and Jordan Form - YouTube

  Every square matrix \(A\) is similar to a Jordan matrix \(J\).

  • \( P \) is called the generalized model matrix.
• The number of Jordan blocks corresponding to the form \(\lambda_i I + N\), where \(N\) is a nilpotent matrix with superdiagonal entries being 1.
• Jordan normal form forms a equivalence class of matrices with the equivalence relation of matrix similarity, that is other than family of the diagonalizable matrices.

• Jordan Normal Form 2 | An Example - YouTube
• Calculate the algebraic multiplicity and the geometric multiplicity to determine the Jordan blocks.
• If indeterminate, calculate further:
  • The number of Jordan blocks corresponding to \(\lambda_i\) of size at least \(j\) is: \[ \dim\ker\left((A-\lambda_iI)^j\right) - \dim\ker\left((A-\lambda_i I)^{j-1}\right). \]
  • This is because a Jordan block is of form \(\lambda_i I + N\) and \(N\) has the degree of nilpotency equal to (the number of missing eigenvectors + one).
  • Subtracting the diagonal matrix \(\lambda_i I\) leaves only the nilpotent matrix \(N\), and exponentiating it increments the dimension of the eigenspace, only if there exists the (exponent - 1) missing eigenvectors.

  • Note:

    \begin{align*} \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{bmatrix}^2 & = \begin{bmatrix} 0 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}\\ \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{bmatrix}^3 &= \begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}. \end{align*}

• Decomposition of any rectangular matrix \(A\) into the form: \[ A = U\Sigma V^\top \]
  • where \(U\) and \(V\) are orthogonal matrices and \(\Sigma\) is a diagonal matrix.

• Notice that \(AA^{\rm T}\) and \(A^{\rm T}A\) are each a symmetric square matrix.
• Eigenvectors of \(AA^{\rm T}\) are the left singular vectors of \(A\), and eigenvectors of \(A^{\rm T}A\) are the right singular vectors. On the other hand, the eigenvalues of the both matrices are equal to each other while the leftover eigenvalues are zero.
• \(AA^{\rm T}\) and \(A^{\rm T}A\) are positive semidefinite, which means those eigenvalues are all greater than or equal to zero.
• Square root of those eigenvalues are the singular values.
• The columns of \(U\) are the left singular vectors in descending order, the diagonal entries of \(\Sigma\) are the singular values in descending order, and the columns of \(V\) are the right singular vectors in descending order.
• \(A = U\Sigma V^{\rm T}\).

• Each singular values multiplied by the corresponding left and right singular vectors represents a individual rank.
• Singular value decomposition on the covariance matrix will give the principal components.²
• The singular value is the eigenvalue of both the left and right symmetric matrices.
  • \[ AA^{\rm T} = U\Sigma \Sigma^{\rm T}U^{\rm T} \]
  • \[ A^{\rm T}A = V\Sigma^{\rm T}\Sigma V^{\rm T} \]

• \(i\)th largest singular value is often denoted as \(\sigma_i(A)\).

A Hermitian positive-definite matrix \( A \) is decomposed in terms of a lower triangular matrix \( L \):

\begin{equation*} A = LL^*. \end{equation*}

LDL decomposition requires the diagonal entries to be 1, and introduces D: \( A = LDL^*. \)

A Hermitian positive-definite matrix \( A \) corresponds to an ellipsoid \( x^\top Ax = 1 \). The vectors \( \{ v_i \} \) for conjugate axes can be chosen sequentially to make an upper triangular matrix with the vectors being the column vectors. By the definition of conjugate axes

\begin{equation*} V^{\top}AV = I \end{equation*}

and the \( L \) can now be chosen to be \( L = (V^{-1})^{\top} \).

Similarly, the principal axes can be used to define \( V \). The orthogonal set of vectors can be normalized yielding the orthogonal matrix \( U \) and diagonal matrix \( \Sigma^{-1/2} \) with its entry being the norm of the vectors.:

\begin{equation*} V = U\Sigma^{-1/2}. \end{equation*}

\( A \) is now decomposed into:

\begin{equation*} A = U\Sigma U^{\top}. \end{equation*}

A square real or complex matrix \( A \) can be decomposed into \[ A = UP \] where \( U \) is a unitary matrix and \( P \) is a positive semi-definite Hermitian matrix.

• If \( A \) is invertible the decomposition is unique, with \( P \) being positive-definite.
  • And \( A \) can be uniquely written as \( Ue^X \) where \( X \) is the unique self-adjoint logarithm of the matrix \( P \).

• Two matrices are row equivalent if one can be changed to the other by a sequence of elementary row operations.
• Equivalently, they have the same row space.

• Reversible, therefore it is an equivalence relation.

• Swap: Swap two rows.
• Scale: Multiply a row by a nonzero constant.
• Pivot: Add a multiple of one row to another row.

• Tow \(n\times n\) matrices \(A\) and \(B\) are similar, if there exists a matrix \(M\) such that: \[ M^{-1}AM = B. \]

• Special case of matrix equivalence.
• The eigenvalues are the same.

• Two square matrices \(A\) and \(B\) are congruent if: \[ P^{\rm T}AP = B \] where \(P\) is an invertible matrix.

• It is the change of basis for a quadratic form.
• They are the same bilinear form or quadratic form with respect to different bases.

• Two rectangular \(m\times n\) matrices \(A\) and \(B\) are equivalent if: \[ B = Q^{-1}AP \] where \(Q\) is an 5.5[invertible]] \(m\times m\) matrix, and \(P\) is an invertible \(n\times n\) matrix.

• They are the same linear transformation \(V\to W\) with respect to two different pair of sets of bases of \(V\) and \(W\).

• See p-norm
• For a matrix \(A\colon K^n\to K^m\), \[ \|A\|_p := \sup_{x\neq 0}\frac{\| Ax\|_p}{\|x\|_p}. \]

• \[ \|A\|_{\alpha,\beta} := \sup_{x\neq 0}\frac{\|Ax\|_\beta}{\|x\|_\alpha} \]

• \[ \| A \|_{p,q} := \left(\sum_{j=1}^n \left( \sum_{i=1}^m |a_{ij}|^p \right)^{\frac{q}{p}}\right)^{\frac{1}{q}}. \]
• \[ \|A\|_{p,p} = \|\mathrm{vec}(A)\|_p = \left( \sum_{i=1}^m \sum_{j=1}^n |a_{ij}|^p \right)^{1/p} \]

• \[ \|A\|_\text{max} := \max_{i,j}|a_{ij}| \]

• \(p=1\) yields the Ky-Fan \(n\)-norm, or the nuclear norm \[ \|A\|_1 = \|A\|_* = \mathrm{tr}(\sqrt{A^*A}) = \sum_{i=1}^{\min\{m,n\}} \sigma_i(A) \]
  • since \(A^*A\) is a positive semidefinite matrix, the \(\sqrt{A^*A}\) is well-defined.
  • The nuclear norm \(\|A\|_*\) is a convex envelope of the rank function \(\mathrm{rank}(A)\), so it is often used in mathematical optimization to search for low-rank matrices.
  • Von Neumann's trace inequality and Hölder's inequality for Euclidean space yields:
    • For \(1/p + 1/q = 1\), \( |\mathrm{tr}(A^*B)| \le \|A\|_p\|B\|_q. \)
    • In particular, \[ \|A\|_\text{F}^2 \le \|A\|_p \|A\|_q. \]
• \(p=2\) yields the Frobenius norm, \(p=\infty\) yields the spectral norm.

• \(k=1\) yields the spectral norm.
• \(k=n\) yields the nuclear norm.

• For complex matrices \(\mathbf{A}\) and \(\mathbf{B}\) \[ \langle \mathbf{A}, \mathbf{B}\rangle_{\rm F} = \operatorname{tr}\left(\mathbf{A}^{\dagger}\mathbf{B}\right). \]
• It is the sum of the element-wise products.

• Hilbert-Schmidt Norm
• \[ \|\mathbf{A}\|_{\rm F} = \sqrt{\langle \mathbf{A}, \mathbf{A}\rangle_{\rm F}} \]

• Sesquilinear
• In terms of vectorization: \[ \operatorname{vec}(\mathbf{A})^{\dagger}\operatorname{vec}(\mathbf{B}). \]

• A matrix norm \(\|\cdot\|\) on \(K^{m\times n}\) is consistent with the vector norms \(\|\cdot\|_\alpha\) on \(K^n\) and , \(\|\cdot\|_\beta\) on \(K^m\) if:
  • \[ \forall A\in K^{m\times n}, \forall x\in K^n, \|Ax\|_\beta \le \|A\|\,\|x\|_\alpha \]
• Further, in the special case \(m=n\) and \(\alpha = \beta\), \(\|\cdot\|\) is called compatible with \(\|\cdot\|_\alpha\).

• A matrix norm is monotone if it is monotomic with respect to the Loewner order, that is: \[ A \preccurlyeq B \implies \|A\| \le \|B\|. \]

• Two norms are equivalent if \[ \exists r, s > 0: \forall A \in K^{m\times n}, r\|A\|_\alpha \le \|A\|_\beta \le s\|A\|_\alpha. \]
• All norms on \(K^{m\times n}\) are equivalent. They induce the same topology.
• Moreover, for every matrix norm on \(\mathbb{R}^{n\times n}\), there exists a unique positive real number \(k\) such that \(\ell\|\cdot \|\) is a sub-multiplicative matrix norm for every \(\ell \ge k\).
  • to wit, \(k = \sup\{\|AB\| : \|A\| < 1, \|B\| \le 1\}.\)
• A sub-multiplicative matrix norm \(\|\cdot\|_\alpha\) is said to be minimal, if there exists no sub-multiplicative matrix norm \(\|\cdot\|_\beta\) satisfying \(\|\cdot \|_\beta < \|\cdot\|_\alpha\).

• For two Hermitian matrices \(A, B\) of order \(n\), \[ A \ge B \iff A - B\text{ positive semidefinite} \]
• and \[ A > B \iff A - B \text{ positive definite}. \]